package com.kehao.leetcode.algorithm;


import org.junit.Test;

import javax.sound.midi.Soundbank;

//https://leetcode-cn.com/problems/decode-ways/
public class Solution91 {

    public int numDecodings(String s) {
        int length = s.length();
        int[] dp = new int[length];
        char[] charArray = s.toCharArray();
        if(charArray[0]=='0') return 0;
        dp[0] =1;
        if(s.length()==1) return 1;
        if(twoIsDecoding(s.substring(0,2))){
            if(charArray[1]=='0'){
                dp[1] = 1;
            }else {
                dp[1] = 2;
            }
        }else {
            if(charArray[1]=='0'){
                dp[1] = 0;
            }else {
                dp[1] = 1;
            }
        }
        for (int i = 2; i < length; i++) {
            if(charArray[i]=='0'){
                if(twoIsDecoding(s.substring(i-1,i+1))){
                    dp[i] = dp[i-2];
                }else {
                    dp[i] = 0;
                }
            }else {
                if(twoIsDecoding(s.substring(i-1,i+1))){
                    dp[i] = dp[i-2] +dp[i-1];
                }else {
                    dp[i] = dp[i-1];
                }
            }
        }

        return dp[length-1];

    }

    //两位数作为一个整体，是否是编码
    public boolean twoIsDecoding(String s){
        int num = Integer.parseInt(s);
        if(num<10 ||num>26){
            return false;
        }else{
            return true;
        }
    }


    @Test
    public void myTest1() {
        String s = "27";
        System.out.println(numDecodings(s));
    }

}
